import math
for _ in range(int(input())):
n = int(input());l = list(map(int, input().split()))
d = 0
for i in l:d = math.gcd(d, i)
if d == 1:print(0)
elif math.gcd(d, n) == 1:print(1)
elif math.gcd(d, n-1) == 1:print(2)
else:print(3)#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1, 0);
cin >> a[1];
int g = a[1];
for (int i = 2; i <= n; i++)
{
cin >> a[i];
g = __gcd(g, a[i]);
}
if (g == 1)
{
cout << 0 << endl;
return;
}
for (int i = n; i >= n - 1; i--)
{
if (__gcd(i, g) == 1)
{
cout << n - i + 1 << endl;
return;
}
}
cout << 3 << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
solve();
}
}
742A - Arpa’s hard exam and Mehrdad’s naive cheat | 1492A - Three swimmers |
1360E - Polygon | 1517D - Explorer Space |
1230B - Ania and Minimizing | 1201A - Important Exam |
676A - Nicholas and Permutation | 431A - Black Square |
474B - Worms | 987B - High School Become Human |
1223A - CME | 1658B - Marin and Anti-coprime Permutation |
14B - Young Photographer | 143A - Help Vasilisa the Wise 2 |
320A - Magic Numbers | 1658A - Marin and Photoshoot |
514A - Chewbaсca and Number | 382A - Ksenia and Pan Scales |
734B - Anton and Digits | 1080A - Petya and Origami |
1642D - Repetitions Decoding | 1440A - Buy the String |
1658F - Juju and Binary String | 478A - Initial Bet |
981A - Antipalindrome | 365A - Good Number |
1204B - Mislove Has Lost an Array | 1409D - Decrease the Sum of Digits |
1476E - Pattern Matching | 1107A - Digits Sequence Dividing |